/*
 * @lc app=leetcode.cn id=47 lang=typescript
 *
 * [47] 全排列 II
 */

// @lc code=start
function permuteUnique(nums: number[]): number[][] {
  const backtrack = (nums: number[], idx: number): void => {
    if (idx === nums.length) {
      // 组合是否出现过
      if (hash.has(nums.toString())) return;
      // 记录第一次出现的组合
      hash.add(nums.toString());
      ans.push([...nums]);
      return;
    }
    // 处理全组合
    for (let i = idx; i < nums.length; i++) {
      [nums[i], nums[idx]] = [nums[idx], nums[i]];
      backtrack(nums, idx + 1);
      [nums[i], nums[idx]] = [nums[idx], nums[i]];
    }
  };
  const ans: number[][] = [];
  const hash: Set<string> = new Set();
  backtrack(nums, 0);
  return ans;
}
// @lc code=end
